In modern cellular systems channel coding for speech parameters is performed based usually on convolutional codes designed so that encoders will generate an integer number of coded bits for each input source bit (as opposed to e.g. three coded bits for every two input source bits). Because of the bits added by the coder to provide redundancy to the bit stream, sometimes some of the encoded bits must be deleted before transmission (i.e. punctured) in order to match the rate of bits coming from the bit stream to the rate at which bits are transmitted.
FIG. 6 illustrates some of the principal components of a wireless communication system including a codec (encoder/decoder) using convolutional encoding. At the transmitting end, input bits are encoded by a (channel) encoder 10 including, in order, a convolutional encoder module 10a, a puncturing module 10b, and a serial to parallel conversion followed by an interleaving module 10c. (The input bits are typically already source encoded to remove unnecessary redundancy before arriving at the encoder 10.) After encoding the input bits to provide symbols each corresponding to some number of input bits, the symbols are each used (in turn) to modulate a waveform in a modulator 12, and the modulated waveforms are then communicated to a de-modulator 14 on the receiver side via a transmission channel (here including the actual transmitter and receiver equipment). On the receiving side, after the de-modulator determines a symbol (representing the received encoded bits provided no error in transmission has occurred) corresponding to each received modulate waveform, a channel decoder 11 (including, in order, a module 11c for de-interleaving and converting symbols to bits, a module 11b for inserting punctured bits, i.e. for inserting 0's for each punctured bit according to predefined puncturing tables indicating in the encoder which bits to puncture out and copies of the same tables in the decoder indicating where bits were punctured out and so where to insert zeros, and a convolutional decoder 11a) examines the received symbols and provides a corresponding output bit stream, possibly removing some errors in transmission thanks to the forward error correction capacity of the communication system provided by the convolutional encoder 11a and corresponding decoder 11a. (The interleaving operation is vital when convolutional codes are used, because such codes are designed to cope well with random errors and their performance decreases dramatically if the errors are bursty and interleaving is not used.)
Where all the data bits to be communicated can be assumed to have equal importance, such as when the data bits are not encoded by an encoder module like the encoder module 10a, puncturing is straightforward; in such situations, data bits are simply punctured out evenly over a codec frame to maintain some same average error protection capability over the entire codec frame. For encoded speech signals, the situation is quite different because it is often the case that some coded (encoded) bits are more important to subjective speech quality while errors in other bits cause only some acceptable degradation (roughness) in the transmitted speech signal, and so some of the bits of an encoded speech bit stream have to be more heavily protected (by the bits added by the convolutional encoder) against channel errors than others of the bits; such protection is provided by what are called unequal error protection schemes (UEPs) often used in speech transmission.
Although, the benefit of unequal error protection in the transmission of speech signals is known, some state of the art technologies such as WCDMA (Wideband Code Division Multiple Access) specified by 3GPP (Third Generation Partnership Program) do not fully exploit UEP schemes for speech traffic. In a 3GPP/WCDMA system, UEP is made possible by dividing a speech encoded frame into sub-sequences and by coding them with separate Equal Error Protection (EEP) channel codecs (3GPP TS 25.212) so as to create different sub-sequences having different error protection, with the result that the encoded frame has a rough, stepwise kind of unequal error protection. Such a stepwise UEP scheme is not the most optimal for speech services, but certainly improves the error robustness compared to what is provided by a pure EEP scheme.
The main idea behind using generic channel codecs in a 3GPP/WCDMA system to provide stepwise UEP is to avoid having to use channel codecs specialized to each type of transmitted data. But in case of speech, a specialized codec providing UEP is advantageous, and there are other applications besides speech (such as image coding) that might also be improved by using specialized channel codecs. However, if data from all such applications each had its own traffic channel (one for speech, one for graphics, and so on), system complexity could become unacceptable. As it is, designers of the 3GPP/WCDMA systems have determined that the non-optimality of EEP channel coding can be compensated for by transmitting at higher power.
On the other hand, the (older) GSM (Global System for Mobile Communications) system does use dedicated channels for speech transmission (TCH/FS, TCH/HS, TCH/EFS, TCH/AFS, TCH/AHS, O-TCH/AHS), as set out in 3GPP TS 45.003. The latest channel codecs of GSM have a puncturing system that finds the most optimal error protection for each speech encoded bit, thus maximizing the overall speech quality in the transmission.
FIG. 1 gives an example of bit error rate (BER) distribution for bits in a frame of speech data after encoding by a channel encoder highly optimized for speech transmission and then decoded. Two different bit position classes are shown: class CA includes bit positions from 1 to 64 where the most important bits (bits that are the most critical to subjective speech quality) are conveyed, and also includes bit positions from 65 to 70 where cyclic redundancy check (CRC) bits are inserted into the encoded bit stream for detecting errors in transmission of the data bits of class CA; and class CB includes bit positions from 71 to 177 where the remaining speech encoded bits are carried, those not as critical to subjective speech quality. In the example shown in FIG. 1, as is usually done, all bits were first reordered in the channel encoder according to subjective importance before any other action was performed by the encoder, with the most important bit placed in bit position 1 and the least important bit in bit position 177.
It can be seen that the BER curve for the class CA bits is quite flat (nearly the same for all bits) and of low amplitude, both for the data bits of class CA (highly important to speech quality) and for the CRC bits in class CA. The channel codec is designed to provide such a flat, low-amplitude bit error rate for class CA bit positions because all bits in a frame are usually either kept or discarded depending on the check provided by the CRC bits (i.e. so that an entire whole frame is discarded if any one of the bits belonging to class CA for the frame is in error). Thus, the overall frame error rate (FER) is minimized when the BER within class CA bits is flat and small.
In contrast to errors in class CA, a decoder will typically not reject an entire frame of bits with bit errors in bits in other than class CA, bits which are typically increasingly less important to speech quality (i.e. the bits in the higher bit positions are less important than the bits in the lower bit positions), and so for optimal error protection for such bits, the protection capability decreases as the bit position increases (i.e. as the subjective importance of the source bits decreases).
Since puncturing to achieve rate matching weakens error protection (by removing redundancy), it is obviously advantageous to preferably puncture less important bits before puncturing more important bits.
A convolutional encoder, which is usually implemented as a shift register, can be completely described by a connection diagram, such as the connection diagram 110 of FIG. 7 for a rate R=1/2 encoder (2 output bits for every input bit), showing three delay elements 111a 111b 111c, and two adders 112 114. The code rate R is in general written as k/n indicating that the encoder maps a k-tuple to an n-tuple. It is possible to more concisely describe an encoder than by providing a connection diagram. One more concise specification can be given by stating the values of n, k, and the so-called constraint length K (defined in different ways, such as the number of k-tuples that affect the formation of each n-tuple during encoding). For the encoder of FIG. 7, n=2, k=1, and K=3. Another way is to give the adder connections in the form of either generator vectors or generator polynomials. For example, the rate 1/2 code of FIG. 7 has the generator vectors g1=111 and g2=101, or equivalently, the generator polynomials g1(x)=x2+x+1 and g2(x)=x2+1, where x is the delay and modulo 2 addition is used in all calculations involving the generator polynomials so that, e.g. (x+1)g1(x)=x3+1. (with x having the value of one delay element, i.e. a delay of one sample, x0=1 indicates no delay, x1 indicates a delay of one sample, x2 indicates a delay of two samples, etc.)
A (generator) polynomial produces only one bit at a time, but for an entire frame's worth of bits, each polynomial contributes a bit multiple times, the same number of times for each polynomial. If all input bits to a polynomial have the same importance, then all output bits of the polynomial also have the same importance. Different polynomials have different importance, i.e. all the polynomial do not make an equal contribution to error protection performance of the convolutional code. Some applications, like speech codecs, provide source bits for the convolutional encoder, but all the bits do not have equal subjective importance and thus the output bits from the convolutional encoder do not have equal importance (even if the generator polynomials would have equal contribution to error protection performance). Thus, to puncture preferentially less important bits when manually optimizing puncturing for a codec having a convolutional encoder producing bits that are not all of the same importance (and so to provide an optimized UEP channel codec), the puncturing can be performed on the basis of the different importance of different bits and also on the basis of the different importance of different polynomials associated with the convolutional encoder. In other words, puncturing can be performed on a bit-by-bit basis and also on a polynomial-by-polynomial basis.
Optimized UEP channel codecs for speech traffic transmission exist, but all such codecs exploit dedicated and manually optimized puncturing tables. Existing prior-art systems that use generic (low complexity) algorithms for puncturing, do not use UEP but instead use EEP and unsophisticated puncturing.
The modulation technique used—e.g. 8 phase shift keying (PSK) modulation—is another factor in the design of optimal puncturing for convolutional codes for speech traffic channels, especially when multiple bits are transmitted as a single symbol (e.g. in 8-PSK modulation, 3-bits are conveyed per symbol). In such systems some of the bits in the transmitted symbols may have higher error probability than others. Modulation in such systems causes a phenomenon that is sometimes called “soft puncturing” (of the bits that have the weaker protection) because the modulation technique weakens the error protection just as (hard or real) puncturing does, where bits are actually removed from the bit stream. For example, in 8-PSK modulation, one of the bits of the three bits of a symbol has twice the error probability compared to the other two bits. More specifically, “soft puncturing” is the act of assigning a bit to a position in a bit stream so that when it is converted to a symbol it is in a position having weaker protection.
Although in 3G channel coding there is a clear advantage in using a generic coding method to minimize the channel codec complexity, there is a clear drawback in the way a generic coding method performs (hard) puncturing (i.e. puncturing for rate matching). In generic coding, bits are evenly punctured out of the convolution encoded stream, i.e. independently of what polynomial they are originate from. Such puncturing degrades the error protection capability of the code, because, as mentioned, (the bits from) all the different convolutional polynomials are not equally important. Puncturing of (bits from) some of the polynomials has less impact to the code properties (related to error protection) than puncturing of some other polynomials. Therefore closer control of puncturing (puncturing polynomial by polynomial) would increase the performance of a 3G channel codec.
Other drawbacks in a prior art 3G channel coding system for speech traffic channels are associated with the use of EEP schemes, as also already mentioned. As explained above, the only possible way in a 3G system to introduce some difference in error protection for different importance classes (e.g. CA & CB) is to split the speech encoded data into two or more separate streams and channel encode each using separate convolutional codes and then transmit each in a separate is transport channel, providing “stepwise” UEP. Besides only approximating true UEP, general coding theory states that overall coding efficiency degrades when data being encoded is split into parts and coded separately. Further, stepwise UEP with its several convolutional codes costs more than true UEP, since there is an additional cost associated with the tailing bits of each additional convolutional code.
Current GSM systems use hand-optimized puncturing tables which provide UEP with flat protection for the most important bits and smoothly decreasing protection performance as a function of decreasing bit importance for all other bits. In addition, existing GSM systems use a dedicated transport channel for speech data optimized by exhaustive objective and subjective speech quality evaluation. If the number of different supported speech codecs is increased to provide UEP, the implementation complexity of the entire channel codec increases as does the complexity of the implementation testing. Currently, the number of channel codecs in GSM systems is increasing; the latest speech codecs, called AMR (Adaptive Multi Rate) and AMR-WB (Adaptive Multi Rate-Wide Band) codecs have eight and nine different operation modes (each having an associated channel codec) respectively. Examples of channel modes are: GMSK (Gaussian Medium Shift Keying) full rate, GMSK half-rate, 8-PSK full rate, 8-PSK half rate. Currently there are 25 different channel codecs specified for GSM systems (TCH/FS, TCH/HS, TCH/EFS, TCH/AFS 12.2, TCH/AFS 10.2, TCH/AFS 7.95, TCH/AFS 7.4, TCH/AFS 6.7, TCH/AFS 5.9, TCH/AFS 5.15, TCH/AFS 4.75, TCH/AHS 7.95, TCH/AHS 7.4, TCH/AHS 6.7, TCH/AHS 5.9, TCH/AHS 5.15, TCH/AHS 4.75, O-TCH/AFS 12.2, O-TCH/AFS 10.2, O-TCH/AFS 7.95, O-TCH/AFS 7.4, O-TCH/AFS 6.7, O-TCH/AFS 5.9, O-TCH/AFS 5.15, O-TCH/AFS 4.75), but that number will increase when channel codecs for AMR-WB codec (in GMSK full rate, 8-PSK full rate and 8-PSK half rate channel modes) are specified.
Because the latest GSM channel codecs (for AMR and AMR-WB) have been designed so that their puncturing is optimized for each codec and for each codec mode by manually determining (tuning) a respective puncturing table, there are now many quite large puncturing tables, and so implementing all GSM channel codecs requires a large amount of memory and exhaustive implementation testing (since operation in every mode must be separately tested in a large number of channel conditions).
What is needed is a generalized puncturing algorithm that combines the benefits of manually optimized puncturing tables (providing optimal performance) as in GSM channel codecs, with the benefits of generic puncturing algorithms (providing lower complexity and simpler implementation testing) as in 3G channel codecs.